
package main.new_2024.month_02;


import main.dataStruct.TreeNode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Description: todo 2583. 二叉树中的第 K 大层和
     * 给你一棵二叉树的根节点 root 和一个正整数 k 。
     * 树中的 层和 是指 同一层 上节点值的总和。
     * 返回树中第 k 大的层和（不一定不同）。如果树少于 k 层，则返回 -1 。
     * 注意，如果两个节点与根节点的距离相同，则认为它们在同一层。
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/
 * @Param:
 * @return:
 **/
public class Solution0223 {

    //前序 第一个得到根结点，中序 区分左右子树，左右递归， 后续，最后一个是根节点
    public long kthLargestLevelSum(TreeNode root, int k) {
        if (root == null){
            return  -1L;
        }
//        PriorityQueue<Long> sumList = new PriorityQueue<>(Comparator.reverseOrder());
        List<Long> sumList = new ArrayList<>();
        Queue<TreeNode> queue =new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            long sum = 0L;
            int size = queue.size();
            for (int i =0;i<size;i++){
                TreeNode poll = queue.poll();
                sum += poll.val;
                if (poll.left != null){
                    queue.add(poll.left);
                }
                if (poll.right != null){
                    queue.add(poll.right);
                }
            }
            sumList.add(sum);
        }
        if (sumList.size() < k){
            return  -1L;
        }else {
            sumList = sumList.stream().sorted(Comparator.reverseOrder()).collect(Collectors.toList());
            return sumList.get(k - 1);
        }

    }



}

